#include <jni.h>
#include <string>
#include "LinkedList.hpp"
#include <android/log.h>
#include "ArrayUtil.cpp"
#include "AVL.hpp"

using namespace std;

// 打印函数
void visit(int key, int value) {
    __android_log_print(ANDROID_LOG_ERROR, "TAG", "key = %d , value = %d", key, value);
}

void bubbleSort(int arr[], int len) {
    for (int i = 0; i < len - 1; ++i) { // 外层循环：n-1 步
        // j < len - i - 1
        for (int j = 0; j < len - i - 1; ++j) { // 内层循环：n-1, n-2 ,n-3, ..., 1
            if (arr[j] > arr[j + 1]) { // 上面的-1，因为这边+1会导致角标越界。
                // 交换 一次交换是三次赋值
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}
// 2.标记位法：
// bool exchange = fasle;
// 内存循环中，有交换，exchange = true;  一次内循环结束后。
// 外层循环中，判断，如果没交换（排序好的），break跳出循环（不要再交换排序了）。

// ***选择排序：思想 遍历找出最小的位置，最后与第一个位置进行交换 空间复杂度：O(1)
void selectSort(int arr[], int len) { // 升序排序。
    for (int i = 0; i < len; ++i) {
        int min = i; // 索引值，然后根据索引值交换。
        for (int j = i + 1; j < len; ++j) {
            if (arr[min] > arr[j]) {
                min = j; // 1.找到最小值的位置 index
            }
        }
        swap(arr[i], arr[min]); // 2. min位置 与 第0（i）位置进行交换。以达到排序
    }
}

void print_array(int arr[], int len) {
    for (int i = 0; i < len; ++i) {
        // 这个方法比较复杂 __android_log_print(ANDROID_LOG_ERROR, "TAG", "%d", arr[i]);
        LOGE("%d", arr[i]);
    }
}

extern "C" JNIEXPORT jstring JNICALL
Java_com_darren_jni_MainActivity_stringFromJNI(
        JNIEnv *env,
        jobject /* this */) {
    // [3,1,2,4,5,6,7,10,9,8] // 加入9时 先右再左旋；加入8时(6打破规则)，先右再左旋。
    AVL<int, int> *avl = new AVL<int, int>();
//    avl->put(3, 3);
//    avl->put(2, 2);
//    avl->put(1, 1); // 需要右旋，将3右旋。
//    avl->put(4, 4);
//    avl->put(5, 5); // 需要左旋，将3左旋。4变成节点，3当左节点。

//    avl->put(2, 2);
//    avl->put(0, 0);
//    avl->put(1, 1);

    avl->put(3, 3);
    avl->put(1, 1);
    avl->put(2, 2);
    avl->put(4, 4);
    avl->put(5, 5);
    avl->put(6, 6);
    avl->put(7, 7);
    avl->put(10, 10);
    avl->put(9, 9);
    avl->put(8, 8);

//    avl->remove(3);
//    avl->remove(1); // 删除后，要进行调整。
    avl->remove(4);
    avl->remove(5);
    avl->remove(2);
    avl->remove(10);
    avl->remove(6);
    avl->remove(8);
    avl->remove(9);
    avl->remove(100);

    avl->levelTraverse(visit); // 层序遍历avl树。
    std::string hello = "Hello from C++";
    return env->NewStringUTF(hello.c_str());
}